package com.example.myapplication;

import android.util.Log;

public class Algorithm {

    public Algorithm(){}

    private BTreeNode rootNode;
    private class BTreeNode{
        int data;
        BTreeNode left;
        BTreeNode right;
    }

    public BTreeNode getRootNode() {
        return rootNode;
    }

    public void createBTree(BTreeNode treeNode, int data){

        BTreeNode bTreeNode=treeNode;
        if(bTreeNode == null){
            bTreeNode = new BTreeNode();
            bTreeNode.data=data;
            bTreeNode.left=null;
            bTreeNode.right=null;
            rootNode=bTreeNode;
            return;
        }

        if(data <= bTreeNode.data){
            if(bTreeNode.left == null){
                BTreeNode node = new BTreeNode();
                node.data=data;
                bTreeNode.left=node;
            }else {
                createBTree(bTreeNode.left,data);
            }
        }else {
            if(bTreeNode.right == null){
                BTreeNode node = new BTreeNode();
                node.data=data;
                bTreeNode.right=node;
            }else {
                createBTree(bTreeNode.right,data);
            }
        }
    }

    public void traversalBTreeMiddle(BTreeNode treeNode){
        BTreeNode bTreeNode=treeNode;
        if(bTreeNode == null) return;
        if(bTreeNode.left != null){
            traversalBTreeMiddle(bTreeNode.left);
        }
        Log.e("Algorithm",""+bTreeNode.data);
        if(bTreeNode.right != null){
            traversalBTreeMiddle(bTreeNode.right);
        }
    }

    public int bTreeDeep(BTreeNode treeNode){
        if(treeNode == null) return 0;
        int left = 0;
        if(treeNode.left != null){
            left = bTreeDeep(treeNode.left);
        }
        int right = 0;
        if(treeNode.right !=null){
            right = bTreeDeep(treeNode.right);
        }
        return left > right ? left+1 : right+1;
    }

    public void bubblingSort(int[] data){
        if(data==null || data.length==0) return;
        for(int i=0;i<data.length-1;i++){
            for(int j=0;j<data.length-1-i;j++){
                if(data[j] > data[j+1]){
                    int temp=data[j];
                    data[j]=data[j+1];
                    data[j+1]=temp;
                }
            }
        }

        for(int k=0;k<data.length;k++){
            Log.e("Algorithm",""+data[k]);
        }
    }

    public void quickSort(int[] data,int startIndex,int endIndex){
        if(startIndex >= endIndex) return;
        int key=data[startIndex];
        int i=startIndex;
        int j=endIndex;
        while (true){
            while (i<j && data[j] >= key ){
                j--;
//                if(i==j){
//                    break;
//                }
            }

            if(i<j){
                data[i]=data[j];
            }

            while (i<j && data[i] <= key ){
                i++;
//                if(i==j){
//                    break;
//                }
            }
            if(i<j){
                data[j]=data[i];
            }

            if(i==j){
                data[i]=key;
                //Log.e("Algorithm","key="+data[i]);
                break;
            }
        }

        quickSort(data,startIndex,i-1);
        quickSort(data,i+1,endIndex);

    }

    //用异或找出不是成对出现的数字(奇数次出现的数字)
    //如 int[] data=new int[]{2,2,8,5,1,1,5}，输出8
    int singleNumber(int[] a){
        int res=a[0];
        for(int i=1;i<a.length;i++){
            res^=a[i];
        }
        return res;
    }

}
